package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/26 21:28
 */
public class XORQueriesOfASubarray {


    /**
     * 数学原则题：
     *  如果：a^b^c^d=e
     *  则：a、b、c、d、e当中四个数[n个数也是一样的原则]的异或运算等于另外一个
     * @param arr
     * @param queries
     * @return
     */
    public int[] xorQueries(int[] arr, int[][] queries) {

        int len = arr.length;
        int[] leftXor = new int[len];
        int[] rightXor = new int[len];


        int sumXor;

        leftXor[0] = sumXor = arr[0];
        for (int i = 1; i < len; i++) {
            leftXor[i] = leftXor[i-1] ^ arr[i];
            sumXor ^= arr[i];
        }

        rightXor[len-1] = arr[len-1];
        for (int i = len-2; i >= 0; i--) {
            rightXor[i] = rightXor[i+1] ^ arr[i];
        }


        int qLen = queries.length;

        int[] result = new int[qLen];
        for (int i = 0; i < qLen; i++) {
            result[i] = sumXor;
            if (queries[i][0] > 0) {
                result[i] ^= leftXor[queries[i][0] - 1];
            }
            if (queries[i][1] < len - 1) {
                result[i] ^= rightXor[queries[i][1] + 1];
            }
        }

        return result;
    }

    /**
     * 原理：(a^b^c^d^e) ^ (a^b^c) = d^e
     * @param arr
     * @param queries
     * @return
     */
    public int[] xorQueries2(int[] arr, int[][] queries) {

        int len = arr.length;
        int[] sumXor = new int[len];

        sumXor[0] = arr[0];
        for (int i = 1; i < len; i++) {
            sumXor[i] = sumXor[i-1] ^ arr[i];
        }


        int qLen = queries.length;

        int[] result = new int[qLen];
        for (int i = 0; i < qLen; i++) {
            if (queries[i][0] > 0) {
                result[i] = sumXor[queries[i][1]] ^ sumXor[queries[i][0]-1];
            } else {
                result[i] = sumXor[queries[i][1]];
            }
        }

        return result;
    }
}
